//
// Created by isabella on 25-6-3.
//
#include <Sort.h>

vector<int> ShellSort::sort(vector<int> arr) {
    int len = arr.size();
    for(int gap = len / 2; gap > 0; gap /= 2) {
        insertionSort(arr, gap);
    }
    return arr;
}

void ShellSort::insertionSort(vector<int>& nums,int gap) {
    for(int i=gap;i<nums.size();i+=gap) {
        int ele = nums[i];
        int j = i-gap;
        while(j>=0 && nums[j]>ele) {
            nums[j+gap] = nums[j];
            j-=gap;
        }
        nums[j+gap] = ele;
    }
}